package com.tianyuan.test1;
//链表
/**
 * @author 甜圆
 * @version v1.0.1
 * @date 2025/10/15 15:05
 * @package com.tianyuan.test1
 * @copyright 甜圆
 */

/**
 * 反转链表
 * 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
 * 数据范围:0 ≤ n ≤ 1000
 * 要求：空间复杂度O(1)，时间复杂度O(n）。
 * 如当输入链表{1,2,3}时,
 * 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1]。
 */

/**
 * 通过迭代法调整节点指针方向
 */
public class ReverseListSolution {

    /**添加一个新方法*/
    public ListNode ReverseList(ListNode pHead) {
        ListNode prev = null;  // 记录前一个节点（初始为null，原表头反转后是尾节点）
        ListNode curr = pHead; // 记录当前处理的节点（初始为原表头）

        while (curr != null) {
            ListNode nextTemp = curr.next; // 临时保存当前节点的下一个节点，防止指针丢失
            curr.next = prev;              // 反转当前节点的指针（指向“前一个节点”）
            prev = curr;                   // 前一个节点指针后移
            curr = nextTemp;               // 当前节点指针后移
        }

        return prev; // 循环结束后，prev指向原链表的尾节点（即新链表的表头）
    }





    // 测试方法：创建链表、调用反转、打印结果
    public static void main(String[] args) {
        ReverseListSolution solution = new ReverseListSolution();

        // 构建示例链表：1 → 2 → 3
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;

        // 反转链表
        ListNode reversedHead = solution.ReverseList(node1);

        // 打印反转后的链表（3 → 2 → 1）
        ListNode curr = reversedHead;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
    }
}